// https://www.lintcode.com/problem/rehashing/

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param hashTable: A list of The first node of linked list
     * @return: A list of The first node of linked list which have twice size
     */    
    public ListNode[] rehashing(ListNode[] hashTable) {
        // write your code here
        int oldSize = hashTable.length;
        int newSize = oldSize * 2;
        ListNode[] ret = new ListNode[newSize];
        Arrays.fill(ret, null);
        for (int i = 0; i < oldSize; ++i) {
            ret[i] = hashTable[i];
        }
        for (int i = 0; i < oldSize; ++i) {
            ListNode prev = null;
            ListNode node = hashTable[i];
            while (node != null) {
                int pos = node.val % newSize;
                if (node.val < 0) {
                    pos = newSize - (Math.abs(node.val) % newSize);
                }
                ListNode next = node.next;
                if (pos != i) { // 新的位置
                    next = node.next;
                    ListNode tmp = node;
                    if (prev != null) {
                        prev.next = next;
                    } else {
                        ret[i] = next;
                    }
                    tmp.next = null;
                    ListNode head = ret[pos];
                    if (head == null) {
                        ret[pos] = tmp;
                    } else {
                        while (head.next != null) {
                            head = head.next;
                        }
                        head.next = tmp;
                    }
                    node = next;

                } else { // 位置不动
                    prev = node;
                    node = node.next;
                }
            }
        }
        return ret;
    }
};